/*
STL list 容器(链表)
链表(list)是一种物理存储单元上非连续的一种存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现
链表由一系列结点组成
STL 中的链表是一个双向循环链表
由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移跟后移不支持随机访问，属于双向迭代器
list 优点
  采用动态分配内存，不会造成内存浪费和溢出
  链表执行插入和删除非常方便，修改指针即可，不需要大量移动元素
list 缺点
  链表灵活，但是空间（指针域）和时间（遍历）额外耗费较大
list 有一个重要的性质，插入和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。
总结：STL中list 和 vector是两个最被常用的容器，各有优缺点

list 构造函数
  与 vector, deque 相似
  函数原型
    list<T> lst;  // 默认构造函数
    list(initializer_list<T> il);  // 使用初始化列表 il 构造容器
    list(beg, end);  // 将[beg, end)区间内的元素拷贝给本身
    list(n, elem);  // 将n个elem拷贝给本身
    list(const list& lst);  // 拷贝构造函数

list 赋值和交换
  与 vector, deque 相似
  函数原型
    assign(beg, end);  // 将[beg, end)区间内的数据拷贝给本身
    assign(n, elem);  // 将n个elem拷贝给本身
    list& operator=(const list& lst);  // 重载等号操作符
    swap(lst);  // 将lst与本身互换元素 

list 大小
  与 deque 相似
  函数原型
    empty();  // 返回是否为空
    size();  // 返回容器中元素的个数
    resize(num);  // 与deque 一致
    resieze(num, elem);  // 与deque 一致

list 插入和删除
  与 deque 相似 多了个remove
  函数原型
    push_back(elem);  // 尾部插入
    push_front(elem);  // 头部插入
    pop_back();  // 删除尾部
    pop_front();  // 删除头部
    insert(pos, elem);  // 在pos位置插入elem， 返回新元素的位置，也就是pos
    insert(pos, n, elem); // 在pos位置插入n个elem, 无返回值
    insert(pos, beg, end); // 在pos位置插入[beg, end)区间内的元素 无返回值
    erase(pos);  // 删除pos位置元素，返回下一个元素的位置
    erase(beg, end);  // 删除[pos, end)区间内的元素，返回下一个元素的位置
    clear();  // 清除所有的元素
    remove(elem);  // 删除容器中所有值与elem相等的元素

list 数据存取
  不支持[] 与 at
  函数原型
    front();  // 返回第一个元素
    back();  // 返回最后一个元素

list 反转与排序
  不需要 algorithm 头文件
  函数原型
    reverse();  // 反转 
    sort();  // 排序 自定义的数据需要自己写排序规则 参见example/list_sort.cpp
*/

#include <iostream>
#include <list>
#include <string>
// #include <algorithm>
using namespace std;

template <typename T>
void pring_lst(const list<T> &l)
{
    for (auto it = l.begin(); it != l.end(); it++)
        cout << *it << " ";
    cout << endl;
}

// list 创建
void func1()
{
    cout << "----------------- list contribute ----------------" << endl;
    list<char> l1;  // list<T> l;
    l1.push_back('a');
    l1.push_back('b');
    l1.push_back('c');
    pring_lst<char>(l1);

    list<int> l2 = {1, 2, 3, 4};  // list(initializer_list<T>  il);
    pring_lst<int>(l2);

    list<int> l3(l2.begin(), l2.end());  // list(beg, end);
    pring_lst<int>(l3);

    list<char> l4(5, 'l');  // list(n, elem);
    pring_lst<char>(l4);

    list<char> l5(l4);  // list(cosnt list& lst);
    pring_lst<char>(l5);

}

// list 赋值和互换
void func2()
{
    cout << "----------------- list assign&swap ----------------" << endl;
    list<int> l1 = {1,2,3};
    pring_lst<int>(l1);

    list<int> l2;
    l2.assign(l1.begin(), l1.end());
    pring_lst<int>(l2);

    list<string> l3;
    l3.assign(5, "hi");
    pring_lst<string>(l3);

    list<string> l4;
    l4=l3;
    pring_lst<string>(l4);

    list<string> l5 = {"hello"};
    pring_lst<string>(l5);

    l5.swap(l4);
    pring_lst<string>(l4);
    pring_lst<string>(l5);


}

// list 大小
void func3()
{
    cout << "----------------- list size ----------------" << endl;
    list<string> l1 = {"hi", "c++", "and", "stl"};
    pring_lst<string>(l1);
    cout << "li.empty: " << l1.empty() << " l1.size: " << l1.size() << endl;

    l1.resize(6, "default");
    pring_lst<string>(l1);
}

// list 插入与删除
void func4()
{
    cout << "----------------- list insert&erase ----------------" << endl;
    list<int> l1;
    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_front(9);
    pring_lst<int>(l1);

    l1.pop_back();
    l1.pop_front();
    pring_lst<int>(l1);

    l1.insert(l1.begin(), 8);
    pring_lst<int>(l1);

    l1.erase(l1.begin());
    pring_lst<int>(l1);

    l1.remove(2);
    pring_lst<int>(l1);
}

// list 数据存取
void func5()
{
    cout << "----------------- list read&write ----------------" << endl;
    list<int> l1 = {1,2,3,4};
    pring_lst<int>(l1);

    // cout << "l1 first elem: " << l1[0]<< endl;  // 不支持[]
    // cout << "l1 first elem: " << l1.at(0) << endl;  // 不支持at
    cout << "l1 first elem: " << l1.front() << endl;
    cout << "l1 last elem: " << l1.back() << endl;

    // list 容器的迭代器是双向迭代器，不支持随机访问
    list<int>::iterator it = l1.begin();
    // it = it + 1;  // 不支持跳跃访问，即使是+1


}

// list 反转与排序
void func6()
{
    cout << "----------------- list reverse&sort ----------------" << endl;
    list<int> l1 = {3,5,3,5,6,7,2,1,0,4};
    pring_lst<int>(l1);

    l1.sort();
    pring_lst<int>(l1);

    l1.reverse();
    pring_lst<int>(l1);


}

int main()
{
    func1(); // list 创建
    func2(); // list 赋值和互换
    func3(); // list 大小
    func4(); // list 删除与插入
    func5(); // list 数据存取
    func6(); // list 翻转与排序

    return 0;
}